package leetcode.weekly.week294;

import leetcode.templates.trees.segment.StNode;

//Solution4Test
public class Solution5 {

	int mod = (int) 1e9 + 7;

	public int totalStrength(int[] strength) {
		long ans = 0;
		Node root = new Node(0, (int) 1e5 + 1);
		for (int i = 0; i < strength.length; i++) {
			int cur = strength[i];
			root.add(i, cur);
		}
		return (int) ans;
	}

	public class Node {

		private int LeftRange, Mid, RightRange;
		private Node leftChild, rightChild;
		private Integer value;
		private long sum;
		private int min;

		public Node(int left, int right) {
			this.LeftRange = left;
			this.RightRange = right;
			this.Mid = ((this.RightRange - this.LeftRange) >> 1) + this.LeftRange;
			this.value = 0;
			this.min = Integer.MAX_VALUE;
			this.sum = 0;
		}

		public void add(int i, int cur) {
			this.add(i, i, cur);
		}

		private Node leftNode() {
			if (this.leftChild == null) {
				this.leftChild = new Node(this.LeftRange, this.Mid);
			}
			return this.leftChild;
		}

		private Node rightNode() {
			if (this.rightChild == null) {
				this.rightChild = new Node(this.Mid + 1, this.RightRange);
			}
			return this.rightChild;
		}

		private void addValue(int value) {
			this.value = this.value == null ? value : this.value + value;
		}

		public void add(int left, int right, int add) {
			if (left > right) {
				return;
			}
			if (left == this.LeftRange && right == this.RightRange) {
				this.value = add;
				this.min = add;
				this.sum = add;
			} else {
//				pushdown();
				this.leftNode().add(left, Math.min(this.Mid, right), add);
				this.rightNode().add(Math.max(this.Mid + 1, left), right, add);
				this.min = Math.min(this.leftNode().min, this.rightNode().min);
				this.sum = this.leftNode().sum + this.rightNode().sum;
			}
		}

		public int query(int index) {
			if (this.LeftRange == index && index == this.RightRange) {
				return value;
			}
			pushdown();
			if (index <= this.Mid) {
				return this.leftNode().query(index);
			}
			return this.rightNode().query(index);
		}

		private void pushdown() {
			if (this.value != null) {
				this.leftNode().addValue(this.value);
				this.rightNode().addValue(this.value);
				this.value = null;
			}
		}

	}

}
